翻訳と辞書 Words near each other ・ SC Schiltigheim ・ SC Schwanenstadt ・ SC Selongey ・ SC Siemensstadt Rugby ・ SC Skify Lviv ・ SC Sokil ・ SC Steinfort ・ SC Sélestat ・ SC Tasmania 1900 Berlin ・ SC Tavriya Simferopol ・ SC Telstar ・ SBY ・ Sbârcioara River ・ Sběř ・ SC ・ SC (complexity) ・ SC 04 Schwabach ・ SC 07 Bad Neuenahr ・ SC 08 Bamberg ・ SC 11 ・ SC 129 ・ SC 1880 Frankfurt ・ SC 38 ・ SC 39 ・ SC 42 ・ SC 430 ・ SC 7 ・ SC Abbeville ・ SC Adler Pankow ・ SC Alba Dictionary Lists mini英和辞書 mini和英辞書 Webster 1913 Latin-English FOLDOC Wikipedia English ウィキペディア

翻訳と辞書　辞書検索 [ 開発暫定版 ] スポンサード リンク SC (complexity) ： ウィキペディア英語版 SC (complexity) In computational complexity theory, SC (Steve's Class, named after Stephen Cook) is the complexity class of problems solvable by a deterministic Turing machine in polynomial time (class P) and polylogarithmic space (class PolyL) (that is, O((log ''n'')k) space for some constant ''k''). It may also be called DTISP(poly, polylog), where DTISP stands for ''deterministic time and space''. Note that the definition of SC differs from P $\backslash cap$ PolyL, since for the former, it is required that the algorithm runs in both polynomial time and polylogarithmic space; while for the latter, two separate algorithms will suffice: one that runs in polynomial time, and another which runs in polylogarithmic space. (It is unknown whether SC and P $\backslash cap$ PolyL are equivalent). DCFL, the strict subset of context-free languages recognized by deterministic pushdown automata, is contained in SC, as shown by Cook in 1979.〔S. A. Cook. Deterministic CFL's are accepted simultaneously in polynomial time and log squared space. Proceedings of ACM STOC'79, pp. 338–345. 1979.〕 It is open if directed st-connectivity is in SC, although it is known to be in P $\backslash cap$ PolyL (because of a DFS algorithm and Savitch's theorem). This question is equivalent to NL ⊆ SC. RL and BPL are classes of problems acceptable by probabilistic Turing machines in logarithmic space and polynomial time. Noam Nisan showed in 1992 the weak derandomization result that both are contained in SC.〔.〕 In other words, given ''polylogarithmic'' space, a deterministic machine can simulate ''logarithmic'' space probabilistic algorithms. == References == 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「SC (complexity)」の詳細全文を読む スポンサード リンク 翻訳と辞書 : 翻訳のためのインターネットリソース Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.